#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

typedef enum _ObjectType
{
	OBJECT_TYPE_INT = 0,
	OBJECT_TYPE_PAIR = 1,
}ObjectType;

enum
{
	MARK_FLAG_NO = 0,
	MARK_FLAG_YES = 1,
};

typedef struct _Object
{
	ObjectType objType;
	int mark_flag;
	struct _Object* pNext;
	union
	{
		int int_value;
		struct
		{
			struct _Object* pCar;
			struct _Object* pCdr;
		};
	};
}Object;

#define MAX_STACK_SIZE	0x0010
typedef struct _VM
{
	Object* pHeader;
	int cur_stack_index;
	Object* stack_array[MAX_STACK_SIZE];
}VM;

VM g_vm;

void vm_init(VM* pVm)
{
	memset(pVm->stack_array, 0x00, sizeof(pVm->stack_array));
	pVm->cur_stack_index = 0;
	pVm->pHeader = NULL;
}

Object* vm_new_object(VM* pVm, ObjectType objType)
{
	Object* pObj = (Object*)malloc(sizeof(Object));
	pObj->objType = objType;
	pObj->mark_flag = MARK_FLAG_NO;

	pObj->pNext = pVm->pHeader;
	pVm->pHeader = pObj;

	return pObj;
}

Object* vm_push(VM* pVm, Object* pObj)
{
	assert(pVm->cur_stack_index < MAX_STACK_SIZE);
	pVm->stack_array[pVm->cur_stack_index++] = pObj;
	return pObj;
}

Object* vm_pop(VM* pVm)
{
	Object* pObj;

	assert(pVm->cur_stack_index >= 0);
	pObj = pVm->stack_array[--pVm->cur_stack_index];
	return pObj;
}

void vm_push_int(VM* pVm, int v)
{
	Object* pObj;

	pObj = vm_new_object(pVm, OBJECT_TYPE_INT);
	pObj->int_value = v;
	vm_push(pVm, pObj);
}

void vm_push_pair(VM* pVm)
{
	Object* pObj;

	pObj = vm_new_object(pVm, OBJECT_TYPE_PAIR);
	pObj->pCar = vm_pop(pVm);
	pObj->pCdr = vm_pop(pVm);
	vm_push(pVm, pObj);
}

void vm_mark_object(Object* pObj)
{
	if (pObj->mark_flag)
	{
		return;
	}
	else
	{
		if (pObj->objType == OBJECT_TYPE_INT)
		{
			pObj->mark_flag = MARK_FLAG_YES;
		}
		else if (pObj->objType == OBJECT_TYPE_PAIR)
		{
			vm_mark_object(pObj->pCar);
			vm_mark_object(pObj->pCdr);
		}
		else
		{
			assert(0);
		}
	}
}

void vm_mark_all(VM* pVM)
{
	int i;
	Object* pObj;

	for (i = 0; i < pVM->cur_stack_index; ++i)
	{
		pObj = pVM->stack_array[i];
		vm_mark_object(pObj);
	}
}

void vm_sweep(VM* pVM)
{
	Object* pDelete;
	Object** ppObj;

	ppObj = &(pVM->pHeader);
	while ((*ppObj) != NULL)
	{
		if ((*ppObj)->mark_flag == MARK_FLAG_YES)
		{
			(*ppObj)->mark_flag = MARK_FLAG_NO;
			ppObj = &((*ppObj)->pNext);
		}
		else
		{
			pDelete = *ppObj;
			*ppObj = pDelete->pNext;
			free(pDelete);
		}
	}
}

void vm_dump(VM* pVM)
{
	Object* pObj;
	pObj = pVM->pHeader;
	while (pObj != NULL)
	{
		if (pObj->objType == OBJECT_TYPE_INT)
		{
			printf("INT: %d\n", pObj->int_value);
		}
		else if (pObj->objType == OBJECT_TYPE_PAIR)
		{
			int a;
			int b;
			b = pObj->pCar->int_value;
			a = pObj->pCdr->int_value;
			printf("PAIR: %d %d\n", a, b);
		}
		else
		{
			assert(0);
		}
		pObj = pObj->pNext;
	}
}

int main()
{
	Object* p1;
	Object* p2;
	Object* p3;

	vm_init(&g_vm);
	
	p1 = vm_new_object(&g_vm, OBJECT_TYPE_INT);
	p1->int_value = 1;

	p2 = vm_new_object(&g_vm, OBJECT_TYPE_INT);
	p2->int_value = 2;

	p3 = vm_new_object(&g_vm, OBJECT_TYPE_INT);
	p3->int_value = 3;

	vm_push(&g_vm, p1);
	vm_push(&g_vm, p3);

	vm_dump(&g_vm);

	vm_mark_all(&g_vm);
	vm_sweep(&g_vm);

	vm_dump(&g_vm);
	return 0;
}
